{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #乘积小于 K 的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSubarrayProductLessThanK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #乘积小于 K 的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数数组&nbsp;<code>nums</code>和整数 <code>k</code>&nbsp;，请找出该数组内乘积小于&nbsp;<code>k</code>&nbsp;的连续的子数组的个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [10,5,2,6], k = 100\n",
    "<strong>输出:</strong> 8\n",
    "<strong>解释:</strong> 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。\n",
    "需要注意的是 [10,5,2] 并不是乘积小于100的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3], k = 0\n",
    "<strong>输出:</strong> 0</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:&nbsp;</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 713&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/subarray-product-less-than-k/\">https://leetcode-cn.com/problems/subarray-product-less-than-k/</a>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ZVAVXX](https://leetcode.cn/problems/ZVAVXX/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ZVAVXX](https://leetcode.cn/problems/ZVAVXX/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k<=1:\n",
    "             return 0\n",
    "        n = len(nums)\n",
    "        prod = 1 \n",
    "        left = 0\n",
    "        ans = 0\n",
    "        for right , x in enumerate(nums):\n",
    "            prod*=x\n",
    "            while prod>=k:\n",
    "                prod /= nums[left]\n",
    "                left+=1\n",
    "            ans += right-left+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        k = log(k)\n",
    "        n = len(nums) + 1\n",
    "        pre_log_sum = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            pre_log_sum[i+1] = pre_log_sum[i] + log(num)\n",
    "        \n",
    "        def binary_select(left: int, right: int, target: float):\n",
    "            while left < right:\n",
    "                mid = left + (right - left + 1) // 2\n",
    "                if pre_log_sum[mid] <= target:\n",
    "                    left = mid \n",
    "                else:\n",
    "                    right = mid - 1\n",
    "         \n",
    "            return left\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(n-1):\n",
    "            #  double 类型只能保证15 位有效数字是精确的，\n",
    "            # -1e-10防止不等式两边数值相等却被判定为大于的情况。\n",
    "            target = pre_log_sum[i] + k - 1e-10\n",
    "            r = binary_select(i+1, n-1, target)\n",
    "            if r < n and pre_log_sum[r] >= target:\n",
    "                continue\n",
    "            cnt += r - i \n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        ans, n = 0, len(nums)\n",
    "        logPrefix = [0] * (n + 1)\n",
    "        for i, num in enumerate(nums):\n",
    "            logPrefix[i + 1] = logPrefix[i] + log(num)\n",
    "        logK = log(k)\n",
    "        for j in range(1, n + 1):# 枚举右边界\n",
    "            l = bisect_right(logPrefix, logPrefix[j] - logK + 1e-10, 0, j)#返回大于logPrefix[j] - logK + 1e-10的第一个位置\n",
    "            ans += j - l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        ans, n = 0, len(nums)\n",
    "        logPrefix = [0] * (n + 1)\n",
    "        for i, num in enumerate(nums):\n",
    "            logPrefix[i + 1] = logPrefix[i] + log(num)\n",
    "        logK = log(k)\n",
    "        for j in range(1, n + 1):\n",
    "            l = bisect_right(logPrefix, logPrefix[j] - logK + 1e-10, 0, j)\n",
    "            ans += j - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k==0: return 0\n",
    "        n = len(nums)\n",
    "        logprefix = [0]*(1+n)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            logprefix[i+1] = logprefix[i] + log(nums[i])\n",
    "        for j in range(1,n+1):\n",
    "            l = bisect_right(logprefix,logprefix[j]-log(k)+1e-10,0,j)\n",
    "            ans += j-l \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        ans, n = 0, len(nums)\n",
    "        logPrefix = [0] * (n + 1)\n",
    "        for i, num in enumerate(nums):\n",
    "            logPrefix[i + 1] = logPrefix[i] + log(num)\n",
    "        logK = log(k)\n",
    "        for j in range(1, n + 1):\n",
    "            l = bisect_right(logPrefix, logPrefix[j] - logK + 1e-10, 0, j)\n",
    "            ans += j - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0: return 0\n",
    "        n = len(nums)\n",
    "        logPrefix = [0]\n",
    "        for num in nums:\n",
    "            logPrefix.append(logPrefix[-1]+math.log(num, 10))\n",
    "\n",
    "        logk = math.log(k, 10)\n",
    "\n",
    "        ans = 0\n",
    "        for j in range(1, n+1):\n",
    "            bound = bisect.bisect_right(logPrefix, logPrefix[j]-logk+1e-10, 0, j)\n",
    "            ans += j-bound\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和+二分查找\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        preSum = [0]\n",
    "        for num in nums:\n",
    "            preSum.append(log(num) + preSum[-1])\n",
    "        n = len(preSum)\n",
    "        ans = 0\n",
    "        logk = log(k)\n",
    "        for l in range(n):\n",
    "            r = bisect.bisect_left(preSum, log(k) + preSum[l], lo=l)\n",
    "            if r - l - 1 > 0:\n",
    "                ans += r - l - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        ans, n = 0, len(nums)\n",
    "        logPrefix = [0] * (n + 1)\n",
    "        for i, num in enumerate(nums):\n",
    "            logPrefix[i + 1] = logPrefix[i] + log(num)\n",
    "        logK = log(k)\n",
    "        for j in range(1, n + 1):\n",
    "            l = bisect_right(logPrefix, logPrefix[j] - logK + 1e-10, 0, j)\n",
    "            ans += j - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        tmp_sum = 1\n",
    "        count = 0\n",
    "        l, r = 0, 0\n",
    "        while r < len(nums):\n",
    "            tmp_sum = tmp_sum * nums[r]\n",
    "            while tmp_sum >= k and l <= r:\n",
    "                tmp_sum /= nums[l]\n",
    "                l += 1\n",
    "            count = count + (r - l + 1)\n",
    "            r += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k<=1:\n",
    "            return 0\n",
    "\n",
    "        ans=0\n",
    "        prod=1\n",
    "        left=0\n",
    "        for right,x in enumerate(nums):\n",
    "            prod*=x\n",
    "            while prod>=k:\n",
    "                prod/=nums[left]\n",
    "                left+=1\n",
    "            ans+=right-left+1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        def bin_search(arr, tar, lo, hi):\n",
    "            if lo > hi:\n",
    "                return hi\n",
    "            m = int((lo + hi) / 2)\n",
    "            if tar <= arr[m]:\n",
    "                return bin_search(arr, tar, lo, m - 1)\n",
    "            else:\n",
    "                return bin_search(arr, tar, m + 1, hi)\n",
    "\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        \n",
    "        logprefix = [0 for _ in range(len(nums) + 1)]\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            logprefix[i] = logprefix[i - 1] + math.log(nums[i - 1])\n",
    "        logK = math.log(k)\n",
    "\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            tar = logprefix[i] + logK\n",
    "            if tar > logprefix[-1]:\n",
    "                j = len(logprefix) - i - 2\n",
    "            else:\n",
    "                j = bin_search(logprefix[i + 1:], tar, 0, len(logprefix) - i - 2)\n",
    "            result += j + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k==0:\n",
    "            return 0\n",
    "        l = r = 0\n",
    "        len_ = len(nums)\n",
    "        prod = nums[0]\n",
    "        cnt = 0\n",
    "        for l, v in enumerate(nums):\n",
    "            if l!=0:\n",
    "                prod = prod/nums[l-1]\n",
    "            while r+1< len_ and prod*nums[r+1] < k:\n",
    "                r +=1\n",
    "                prod *= nums[r]\n",
    "            \n",
    "            cnt += r-l+1\n",
    "            print(r-l+1)\n",
    "\n",
    "\n",
    "\n",
    "        return cnt \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k<=1:\n",
    "            return 0\n",
    "        l=0\n",
    "        s=1\n",
    "        ans=0\n",
    "        for r,right in enumerate(nums):\n",
    "            s*=right\n",
    "            while s>=k:\n",
    "                s/=nums[l]\n",
    "                l+=1\n",
    "            ans+=r-l+1\n",
    "        return ans\n",
    "            \n",
    "                          \n",
    "            \n",
    "                    \n",
    "                \n",
    "                \n",
    "            \n",
    "                \n",
    "                \n",
    "                \n",
    "                 \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        total = 1\n",
    "        i = 0\n",
    "        for j, num in enumerate(nums):\n",
    "            total *= num\n",
    "            while i <= j and total >= k:\n",
    "                total /= nums[i]\n",
    "                i += 1\n",
    "            count += j - i + 1\n",
    "        return count\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if min(nums) > k:\n",
    "            return 0\n",
    "\n",
    "        mul_num = [0]\n",
    "        for i in nums:\n",
    "            mul_num.append(mul_num[-1]+log(i))\n",
    "       \n",
    "        i = 0\n",
    "        j = 1\n",
    "        res = 0\n",
    "        while j < len(mul_num):\n",
    "            if mul_num[j] - mul_num[i] < log(k)-1e-10:\n",
    "                res += j - i\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "            if i == j:\n",
    "                j = i + 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "        # ans, prod, i = 0, 1, 0\n",
    "        # for j, num in enumerate(nums):\n",
    "        #     prod *= num\n",
    "        #     while i <= j and prod >= k:\n",
    "        #         prod //= nums[i]\n",
    "        #         i += 1\n",
    "        #     ans += j - i + 1\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n, i, p = 0, 0, 1\n",
    "        for j, num in enumerate(nums):\n",
    "            p *= num\n",
    "            while p >= k and i <= j:\n",
    "                p //= nums[i]\n",
    "                i += 1\n",
    "            n += j - i + 1\n",
    "        return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res, prod, i = 0, 1, 0 \n",
    "        # n = len(nums)\n",
    "        for j, num in enumerate(nums):\n",
    "            prod *= num\n",
    "            while i <= j and prod >=k:\n",
    "                prod //= nums[i]\n",
    "                i += 1\n",
    "            res += j-i+1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans,prod,i=0,1,0\n",
    "        for j, num in enumerate(nums):\n",
    "            prod *= num\n",
    "            while i<=j and prod>=k:\n",
    "                prod//=nums[i]\n",
    "                i+=1\n",
    "            ans+=j-i+1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 双指针，考虑左右边界和子数组个数之间的关系\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        temp = 1\n",
    "        res = 0\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        for right in range(len(nums)):\n",
    "            temp = temp * nums[right]\n",
    "            while temp >= k:\n",
    "                temp = temp/nums[left]\n",
    "                left += 1\n",
    "            res = res + right - left + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 0:\n",
    "            return 0\n",
    "\n",
    "        ret = 0\n",
    "        product = 1\n",
    "        left = 0; right = 0\n",
    "        while True:\n",
    "            # 累乘当前右端\n",
    "            product *= nums[right]\n",
    "            # 如果超过k，那么移动左端\n",
    "            while left <= right and product >= k:\n",
    "                product //= nums[left]\n",
    "                left += 1\n",
    "            ret += right - left + 1 # 当前窗口满足条件，计入\n",
    "            # 滑窗右移\n",
    "            right += 1\n",
    "            if right >= len(nums):\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        tmp = 1\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            tmp *= num\n",
    "            while left <= right and tmp >= k:\n",
    "                tmp /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "            \n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        total = 1\n",
    "        i, j = 0, 0\n",
    "        while i < len(nums):\n",
    "            if j != len(nums): \n",
    "                if j < i: j =i\n",
    "                total *= nums[j]\n",
    "            else:\n",
    "                count += (j - i) * (j - i + 1) / 2\n",
    "                break\n",
    "            if total >= k:\n",
    "                count += j - i\n",
    "                i += 1\n",
    "                total /= nums[i - 1] * nums[j]\n",
    "            else:\n",
    "                j += 1\n",
    "        return int(count)\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        while k==0:\n",
    "            if 0 not in nums:\n",
    "                return 0\n",
    "        left,right,res,sum_=0,0,0,1\n",
    "        while right<len(nums):\n",
    "            sum_*=nums[right]\n",
    "            while left <= right and sum_>=k:\n",
    "                sum_/=nums[left]\n",
    "                left+=1\n",
    "            if left<=right:\n",
    "                res+=right-left+1\n",
    "            right+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        left = ret = 0\n",
    "        total = 1\n",
    "        for right, num in enumerate(nums):\n",
    "            total *= num\n",
    "            while left <= right and total >= k:\n",
    "                total //= nums[left]\n",
    "                left += 1\n",
    "            if left <= right:\n",
    "                ret += right - left + 1\n",
    "        \n",
    "        return ret\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans, s, j = 0, 1, 0\n",
    "        for i, v in enumerate(nums):\n",
    "            s *= v\n",
    "            while j <= i and s >= k:\n",
    "                s //= nums[j]\n",
    "                j += 1\n",
    "            ans += i - j + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        if k<=1 or n<1:\n",
    "            return 0\n",
    "        left=0\n",
    "        right=0\n",
    "        ans=0\n",
    "        res=1\n",
    "        for x in nums:\n",
    "            res*=x\n",
    "            while res>=k:\n",
    "                res=res/nums[left]\n",
    "                left+=1\n",
    "            ans+=right-left+1\n",
    "            right+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans, prod, i = 0, 1, 0\n",
    "        for j, num in enumerate(nums):\n",
    "            prod *= num\n",
    "            while i <= j and prod >= k:\n",
    "                prod //= nums[i]\n",
    "                i += 1\n",
    "            ans += j - i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        ans = left = 0\n",
    "        prod = 1\n",
    "        for right, x in enumerate(nums):\n",
    "            prod *= x\n",
    "            while prod >= k:  # 不满足要求\n",
    "                prod /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        left = right = 0\n",
    "        n = len(nums)\n",
    "        curr = 1\n",
    "        while right < n:\n",
    "            curr *= nums[right]\n",
    "            right += 1\n",
    "            while left < right and curr >= k:\n",
    "                curr //= nums[left]\n",
    "                left += 1\n",
    "            if curr < k:\n",
    "                res += (right - left)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 双指针，考虑左右边界和子数组个数之间的关系\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        temp = 1\n",
    "        ans = 0\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        for right in range(len(nums)):\n",
    "            temp = temp * nums[right]\n",
    "            while temp >= k:\n",
    "                temp = temp/nums[left]\n",
    "                left += 1\n",
    "            ans = ans + right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        p = 1\n",
    "        ans = 0\n",
    "        left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            p *= num\n",
    "\n",
    "            while left <= right and p >= k:\n",
    "                p /= nums[left]\n",
    "                left += 1\n",
    "\n",
    "            if p < k:\n",
    "                ans += right - left + 1  # !!!!!!!!!! 以right为右端点的区间数\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans, tmp, start = 0, 1, 0\n",
    "\n",
    "        for ind, num in enumerate(nums):\n",
    "            tmp *= num\n",
    "            while start <= ind and tmp >= k:\n",
    "                tmp //= nums[start]\n",
    "                start += 1\n",
    "            ans += ind - start + 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        lnums=len(nums)\n",
    "        l,r=0,0\n",
    "        product=1\n",
    "        while r<lnums:\n",
    "            product*=nums[r]\n",
    "            while l<=r and product>=k:\n",
    "                product/=nums[l]\n",
    "                l+=1\n",
    "            ans+=r-l+1 if r>=l else 0\n",
    "            r+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        j = 0\n",
    "        mutiply = 1\n",
    "        for i in range(0,n):\n",
    "            while j < n:\n",
    "                if mutiply*nums[j]<k:\n",
    "                    mutiply*=nums[j]\n",
    "                    j+=1\n",
    "                else:\n",
    "                    mutiply/=nums[i]\n",
    "                    break\n",
    "            result += j-i\n",
    "            j=max(i+1,j)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        ans = left = 0\n",
    "        prod = 1\n",
    "        for right, x in enumerate(nums):\n",
    "            prod *= x\n",
    "            while prod >= k:  # 不满足要求\n",
    "                prod /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        s, v, l, ret = 0, 1, len(nums), 0\n",
    "        for i in range(l):\n",
    "            n = nums[i]\n",
    "            v = v * n\n",
    "            while v >= k and i - s > 0:\n",
    "                t = nums[s]\n",
    "                s += 1\n",
    "                v = v // t\n",
    "            if v >= k:\n",
    "                v = 1\n",
    "                s = i + 1\n",
    "            ret = ret + (i - s + 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        prod = 1\n",
    "        ans = 0\n",
    "        slow,fast =0,0\n",
    "        n = len(nums)\n",
    "        while fast<n:\n",
    "            prod*=nums[fast]\n",
    "            while prod>=k and slow<=fast:\n",
    "                prod//=nums[slow]\n",
    "                slow += 1\n",
    "            ans += fast-slow+1\n",
    "            fast += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        left,right = 0,0\n",
    "        curProd = 1\n",
    "        while right < len(nums):\n",
    "            curProd *= nums[right]\n",
    "            while left <= right and curProd >= k:\n",
    "                curProd /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "            right += 1\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        ret = 0\n",
    "        product = 1\n",
    "        left = 0; right = 0\n",
    "        while True:\n",
    "            # 累乘当前右端\n",
    "            product *= nums[right]\n",
    "            # 如果超过k，那么移动左端\n",
    "            while left <= right and product >= k:\n",
    "                product //= nums[left]\n",
    "                left += 1\n",
    "            ret += right - left + 1 # 当前窗口满足条件，计入\n",
    "            # 滑窗右移\n",
    "            right += 1\n",
    "            if right >= len(nums):\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        l,res,ans=0,1,0\n",
    "        for r in range(n):\n",
    "            res*=nums[r]\n",
    "            while res>=k and l<=r:\n",
    "                res/=nums[l]\n",
    "                l+=1\n",
    "            if r>=l:\n",
    "                ans+=r-l+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        l=0\n",
    "        s=1\n",
    "        ans=0\n",
    "        for r in range(n):\n",
    "            x=nums[r]\n",
    "            s*=x\n",
    "            while l<=r and s>=k:\n",
    "                s/=nums[l]\n",
    "                l+=1\n",
    "            ans+=(r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        j = 0\n",
    "        mutiply = 1\n",
    "        for i in range(0,n):\n",
    "            while j < n:\n",
    "                if mutiply*nums[j]<k:\n",
    "                    mutiply*=nums[j]\n",
    "                    j+=1\n",
    "                else:\n",
    "                    mutiply/=nums[i]\n",
    "                    break\n",
    "            result += j-i\n",
    "            j=max(i+1,j)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        total = 1\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        for right, x in enumerate(nums):\n",
    "            total *= x\n",
    "            while total >= k:\n",
    "                total /= nums[left]\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        total = 1\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        for right, x in enumerate(nums):\n",
    "            total *= x\n",
    "            while total >= k:\n",
    "                total /= nums[left]\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        product = 1\n",
    "        res = 0\n",
    "\n",
    "        while right < len(nums):\n",
    "            product *= nums[right]\n",
    "            right += 1\n",
    "            while left < right and product >= k:\n",
    "                product = product//nums[left]\n",
    "                left += 1\n",
    "            res += (right - left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        s, v, l, ret = 0, 1, len(nums), 0\n",
    "        for i in range(l):\n",
    "            n = nums[i]\n",
    "            v = v * n\n",
    "            while v >= k and i - s > 0:\n",
    "                t = nums[s]\n",
    "                s += 1\n",
    "                v = v // t\n",
    "            if v >= k:\n",
    "                v = 1\n",
    "                s = i + 1\n",
    "            ret = ret + (i - s + 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        ans = left = 0\n",
    "        prod = 1\n",
    "        for right, x in enumerate(nums):\n",
    "            prod *= x\n",
    "            while prod >= k:  # 不满足要求\n",
    "                prod /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k<=1:\n",
    "            return 0\n",
    "            \n",
    "        left = 0\n",
    "        prod = 1\n",
    "        ans = 0\n",
    "        for right,x in enumerate(nums):\n",
    "            prod *= x\n",
    "            while prod >= k:\n",
    "                prod /= nums[left]\n",
    "                left+=1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        prod = 1\n",
    "        i = 0\n",
    "        for j in range(len(nums)):\n",
    "            prod *= nums[j]\n",
    "            while i <= j and prod >= k:\n",
    "                prod //= nums[i]\n",
    "                i+=1\n",
    "        \n",
    "            res += (j - i + 1)\n",
    "                        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        # 双指针，right=i,left=0\n",
    "        # res*=i<k,ans++;res>=k:进入循环left<right;res/=nums[left],小于k;ans++\n",
    "\n",
    "        if min(nums)>=k:return 0\n",
    "        n=len(nums)\n",
    "        left=0\n",
    "        ans=0\n",
    "        res=1\n",
    "\n",
    "        for i in range(n):\n",
    "            res*=nums[i]\n",
    "            while res>=k:\n",
    "                res=res/nums[left]\n",
    "                left+=1\n",
    "            ans+=i-left+1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        l, r = 0, 0\n",
    "        product = 1\n",
    "        while r < len(nums):\n",
    "            product *= nums[r]\n",
    "            while l <= r and product >= k:\n",
    "                product //= nums[l]\n",
    "                l += 1\n",
    "            res += r-l+1\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        res = 0\n",
    "        cur_sum = 1\n",
    "        for right in range(n):\n",
    "            cur_sum *= nums[right]\n",
    "            while left < right and cur_sum >= k:\n",
    "                cur_sum = cur_sum//nums[left]\n",
    "                left += 1\n",
    "            if cur_sum < k:\n",
    "                res += right - left + 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k<=1:\n",
    "            return 0\n",
    "        s = 1\n",
    "        letf = 0\n",
    "        ans = 0\n",
    "        for right,num in enumerate(nums):\n",
    "            s *= num\n",
    "            while s >= k:\n",
    "                s = s / nums[letf]\n",
    "                letf += 1\n",
    "            ans += right -letf +1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        l = r = 0\n",
    "        prod = 1\n",
    "        result = 0\n",
    "        while r < len(nums):\n",
    "            prod = nums[r] * prod\n",
    "            r += 1\n",
    "            while prod >= k and l < r:\n",
    "                prod = prod / nums[l]\n",
    "                l += 1 \n",
    "            result += r-l\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        i,j = 0,0\n",
    "        res = 0\n",
    "        x = 1\n",
    "        while(j<len(nums)):\n",
    "            x *= nums[j]\n",
    "            if x<k:\n",
    "                res += j-i+1\n",
    "            else:\n",
    "                while(i<=j and x>=k):\n",
    "                    x /= nums[i]\n",
    "                    i += 1\n",
    "                res += j-i+1\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        window = 1\n",
    "        l = r = 0\n",
    "        while r < n:\n",
    "            window *= nums[r]\n",
    "            while l <= r and window >= k:\n",
    "                window /= nums[l]\n",
    "                l += 1\n",
    "            if l <= r:\n",
    "                res += r - l + 1\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        count = 0\n",
    "        left = 0\n",
    "        a = 1\n",
    "        for right,value in enumerate(nums):\n",
    "            a *= value\n",
    "            while a >= k:\n",
    "                a /= nums[left]\n",
    "                left += 1\n",
    "            count += right-left+1\n",
    "                \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1: return 0\n",
    "        ans = 0\n",
    "        prod = 1\n",
    "        left = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            prod *= x\n",
    "            while prod >= k:\n",
    "                prod /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 双指针，考虑左右边界和子数组个数之间的关系\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        temp = 1\n",
    "        res = 0\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        for right in range(len(nums)):\n",
    "            temp = temp * nums[right]\n",
    "            while temp >= k:\n",
    "                temp = temp/nums[left]\n",
    "                left += 1\n",
    "            res = res + right - left + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = ans = 0\n",
    "        cur = 1\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        for r, x in enumerate(nums):\n",
    "            cur *= x\n",
    "            while cur >= k:\n",
    "                cur //= nums[l]\n",
    "                l += 1\n",
    "            ans += r - l + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k<=1:return 0\n",
    "        left=0\n",
    "        ans=0\n",
    "        s=1\n",
    "        for right,x in enumerate(nums):\n",
    "            s*=x\n",
    "            while s>=k:\n",
    "                s/=nums[left]\n",
    "                left+=1\n",
    "            ans+=right-left+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        if k <= 0:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        mul = 1\n",
    "        while right < len(nums):\n",
    "            mul *= nums[right]\n",
    "            while mul >= k and left <= right:\n",
    "                mul /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "            right += 1\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        window = 1\n",
    "        l = r = 0\n",
    "        for r in range(n):\n",
    "            window *= nums[r]\n",
    "            while l <= r and window >= k:\n",
    "                window /= nums[l]\n",
    "                l += 1\n",
    "            if l <= r:\n",
    "                res += r - l + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if min(nums) > k:\n",
    "            return 0 \n",
    "        \n",
    "        res = 1\n",
    "        cnt = 0\n",
    "        start = 0\n",
    "        for end in range(len(nums)):\n",
    "            res = res * nums[end]\n",
    "            while start <= end and res >= k:\n",
    "                res = res // nums[start]\n",
    "                start += 1\n",
    "            \n",
    "            if res < k:\n",
    "                cnt += end-start+1 \n",
    "        \n",
    "        return cnt \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = 0, 0\n",
    "        prod = 1\n",
    "        res = 0\n",
    "        while r < n:\n",
    "            prod *= nums[r]\n",
    "            if prod < k:\n",
    "                res += r-l+1\n",
    "            else:\n",
    "                while (l<=r) and (prod >= k):\n",
    "                    prod /= nums[l]\n",
    "                    l += 1\n",
    "                res += r-l+1\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        cur = 1\n",
    "        left = 0\n",
    "        for right in range(n):\n",
    "            cur *= nums[right]\n",
    "            while left <= right and cur >= k:\n",
    "                cur /= nums[left]\n",
    "                left += 1\n",
    "            # 当窗口内的乘积cur < k时，满足条件个数 = right - left + 1\n",
    "            res += right - left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "\n",
    "        # 左开右闭区间\n",
    "        cur_multiply = 1\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            cur_multiply *= nums[right]\n",
    "\n",
    "            # 滑动左边窗口，直到乘积小于k\n",
    "            while left < right and cur_multiply >= k:\n",
    "                cur_multiply /= nums[left]\n",
    "                left += 1\n",
    "            \n",
    "            if cur_multiply < k:\n",
    "                res += (right - left + 1)\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        begin = 0\n",
    "        curr = 1\n",
    "        ans = 0\n",
    "        for end, n in enumerate(nums):\n",
    "            curr *= n\n",
    "            while begin <= end and curr >= k:\n",
    "                curr //= nums[begin]\n",
    "                begin += 1\n",
    "            ans += end - begin + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        first=0\n",
    "        second=0\n",
    "        total=1\n",
    "        m=len(nums)\n",
    "        while second<m:\n",
    "            total*=nums[second]\n",
    "            while first<=second and total>=k:\n",
    "                total//=nums[first]\n",
    "                first+=1\n",
    "            res+=second-first+1\n",
    "            second+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        multi = 1\n",
    "\n",
    "        for right, x in enumerate(nums):\n",
    "            multi *= x\n",
    "            while multi >= k:\n",
    "                multi /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        l, r = 0, 0 \n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        _mul = 1\n",
    "\n",
    "        while r < n:\n",
    "            _mul *= nums[r]\n",
    "\n",
    "            while l <= r and _mul >= k:\n",
    "                _mul = _mul // nums[l]\n",
    "                l += 1\n",
    "                \n",
    "            count += (r - l + 1)\n",
    "            r += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0 or k == 1:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        ans = 0\n",
    "        cur = 1\n",
    "        while p2 < n:\n",
    "            cur *= nums[p2]\n",
    "            if cur >= k:\n",
    "                while cur >= k:\n",
    "                    cur //= nums[p1]\n",
    "                    ans += p2 - p1\n",
    "                    p1 += 1\n",
    "            p2 += 1\n",
    "        ans += (p2 - p1)*(p2 - p1 + 1)//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        rs = 0\n",
    "        l = len(nums)\n",
    "        st, ed = 0, 0\n",
    "        multi_tmp = 1\n",
    "        while ed < l:  # 先定右边界\n",
    "            multi_tmp *= nums[ed]\n",
    "\n",
    "            while st<=ed and multi_tmp>=k:  # 缩窗口，找到<k的连续子区间\n",
    "                multi_tmp //= nums[st]\n",
    "                st += 1\n",
    "            rs += ed-st+1  # 右边界固定，左边界可取个数为当前区间长度\n",
    "\n",
    "            ed += 1\n",
    "\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        # [l,r] < k\n",
    "        # [l+1,r],[l+2,r],...[r,r]都满足，有r-l+1个元满足\n",
    "        if k == 0 or k == 1:\n",
    "            return 0\n",
    "        cnt = 0\n",
    "        left = 0\n",
    "        mul = 1\n",
    "        for right,x in enumerate(nums):\n",
    "            mul *= x\n",
    "            while mul >= k:\n",
    "                mul //= nums[left]\n",
    "                left += 1\n",
    "            cnt += (right - left + 1)\n",
    "            right += 1\n",
    "        return max(cnt,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        res = 0\n",
    "        left, right = 0, 0\n",
    "        tmp = 1\n",
    "        while right < n:\n",
    "            tmp = tmp * nums[right]\n",
    "            right += 1\n",
    "            while tmp >= k:\n",
    "                # print(nums[left])\n",
    "                tmp = tmp / nums[left]\n",
    "                left += 1\n",
    "            res += right - left\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        slow, fast, ret, prod = 0, 0, 0, 1\n",
    "        while fast < len(nums):\n",
    "            prod *= nums[fast]\n",
    "            while slow <= fast and prod >= k:\n",
    "                prod //= nums[slow]\n",
    "                slow += 1\n",
    "            # 窗口每次移动后，res都可以增加 fast - slow + 1个子数组\n",
    "            # 这句话看不懂\n",
    "            if slow <= fast and prod < k:\n",
    "                ret += fast - slow + 1\n",
    "            fast += 1\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
